package com.atguigu.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * 基数排序：属于分配式排序，又称为桶排序，是通过键值的各个位的值，将要排序的元素分配至某些桶中，达到排序的目的。
 * 将整数按位数进行切分，然后每位分别进行比较。属于稳定性排序，是效率高的稳定性排序法。
 *思想：将所有待比较的数值统一为统一的位数，短的前面补零，然后从最低位开始，一次进行一次排序，这样从最低位排序一直到
 * 最高位排序之后，数列就变成了一个有序的序列。
 * 800w个数据耗时大约1s，效率非常的高
 * 问题：占用的空间巨大，当对8000w个数据进行排序的时候，会出现堆内存不够的情况的出现。
 * 稳定：多个值相等，排序之后相对顺序还是之前的位置，
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr=new int[]{53,3,542,748,14,214};
        radixSort2(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("----------------------------------");
        int[] array = new int[8000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(800000000);
        }
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        radixSort2(array);
        System.out.println("排序后的时间：" + System.currentTimeMillis());
        //System.out.println(Arrays.toString(array));

    }

    /**
     * 步骤：1）将每个元素的个位数取出，然后看这个数应该放到哪一个桶中（一个一维数组）
     *      2）按照桶的顺序（一维数组）的下标一次取出数据，放到原来的数组中去。即{53,3,542,748,14,214}=>{542，53，3，14，214，748}
     *      3) 将每个元素的十位取出桶中，然后按照桶的顺序取出数据，放回到原来的数组中去。即{542，53，3，14，214，748}=>{3，14，214，542，738，53}
     *      4）循环以上的操作。
     */
    public static void radixSort(int[] arr) {
        //第一轮排序（针对每个元素的个位进行排序处理）
        //二维数组表示10个桶,每个桶中最多可以存放aar个元素（空间换取时间）
        int[][] bucket=new int[10][arr.length];
        //用来记录每个桶中存放数据的个数。
        int[] bucketEleCounts=new int[10];
        for (int i = 0; i < arr.length; i++) {
            //取出每个元素的个位
            int digitOfEle=arr[i]%10;
            bucket[digitOfEle][bucketEleCounts[digitOfEle]]=arr[i];
            bucketEleCounts[digitOfEle]++;
        }
        int index=0;
        for (int i = 0; i <bucket.length; i++) {
            for (int j = 0; j < bucketEleCounts[i]; j++) {
                arr[index]=bucket[i][j];
                index++;

            }
            //将桶进行初始化
            bucketEleCounts[i]=0;
        }
        //第二轮:
        for (int i = 0; i < arr.length; i++) {
            //取出每个元素的个位
            int digitOfEle=arr[i]/10%10;
            bucket[digitOfEle][bucketEleCounts[digitOfEle]]=arr[i];
            bucketEleCounts[digitOfEle]++;
        }
        index=0;
        for (int i = 0; i <bucket.length; i++) {
            for (int j = 0; j < bucketEleCounts[i]; j++) {
                arr[index]=bucket[i][j];
                index++;

            }
            //将桶进行初始化
            bucketEleCounts[i]=0;
        }
        //第三轮
        for (int i = 0; i < arr.length; i++) {
            //取出每个元素的个位
            int digitOfEle=arr[i]/100%10;
            bucket[digitOfEle][bucketEleCounts[digitOfEle]]=arr[i];
            bucketEleCounts[digitOfEle]++;
        }
        index=0;
        for (int i = 0; i <bucket.length; i++) {
            for (int j = 0; j < bucketEleCounts[i]; j++) {
                arr[index]=bucket[i][j];
                index++;

            }
            //将桶进行初始化
            bucketEleCounts[i]=0;
        }
    }

    /**
     * 基数排序综合版本
     * @param arr:待排序的数目
     */
    public static void radixSort2(int[] arr) {
        int[][] bucket=new int[10][arr.length];
        //用来记录每个桶中存放数据的个数。
        int[] bucketEleCounts=new int[10];
        //求最大的值的位数
        int max=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
        }
        int maxLength=(max+"").length();
        for (int k = 0,n=1; k < maxLength; k++,n*=10) {
            for (int i = 0; i < arr.length; i++) {
                //取出每个元素的个位
                int digitOfEle=arr[i]/n%10;
                bucket[digitOfEle][bucketEleCounts[digitOfEle]]=arr[i];
                bucketEleCounts[digitOfEle]++;
            }
            int index=0;
            for (int i = 0; i <bucket.length; i++) {
                for (int j = 0; j < bucketEleCounts[i]; j++) {
                    arr[index]=bucket[i][j];
                    index++;

                }
                //将桶进行初始化
                bucketEleCounts[i]=0;
            }


        }

    }

}

